package mine.code.question.动态规划;

import org.junit.Test;

/**
 * 给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
 * <p>
 * 示例 :
 * 输入:
 * "bbbab"
 * 输出:
 * 4
 * 一个可能的最长回文子序列为 "bbbb"。
 *
 * @author caijinnan
 * @date 2020/4/8 14:49
 */
public class 最长回文子序列 {

    @Test
    public void run() {
        // babcab
        String s = "abcabcabcabc";
        System.out.println(longestPalindromeSubseq(s));
    }

    // dp[i][j] = at[i]==at[j] dp[i+1][j-1]+2|max(dp[i+1][j],dp[i][j-1])
    public int longestPalindromeSubseq(String s) {
        int length = s.length();
        int[][] dp = new int[length][length];
        for (int i = length-1; i >=0; i--) {
            for (int j = i; j < length; j++) {
                if (i == j) {
                    dp[i][j] = 1;
                } else {
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }else{
                        dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                    }
                }
            }
        }
        return dp[0][length-1];
    }
}